package com.cn.algorithm02.class07;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.concurrent.TimeUnit;

/***
 * @author: hels
 * @description: 手写增强堆，增加反向索引表
 * 反向索引表以及比较器对于基础数据类型需要重新设计，可以包一层
 *
 **/
public class C12_HeapEnhance<T> {

    public static void main(String[] args) {
        C12_HeapEnhance<Integer> heapEnhance = new C12_HeapEnhance<Integer>((o1, o2) -> {
            return o1.compareTo(o2);
        });

        heapEnhance.push(18);
        heapEnhance.push(2);
        heapEnhance.push(12);
        heapEnhance.push(1);
        heapEnhance.push(6);
        heapEnhance.push(5);
        heapEnhance.push(7);
        heapEnhance.push(8);
        System.out.println(heapEnhance);
       heapEnhance.remove(2);
        System.out.println(heapEnhance.getAllElement());
        System.out.println(heapEnhance);
    }

    private ArrayList<T> heap; // 动态数组
    // 反向索引表
    private HashMap<T, Integer> indexMap;
    private int heapSize;
    private Comparator<? super T> comp;

    public C12_HeapEnhance(Comparator<? super T> comp) {
        heap = new ArrayList<>();
        indexMap = new HashMap<>();
        heapSize = 0;
        this.comp = comp;
    }

    public boolean isEmpty() {
        return heapSize == 0;
    }

    public int size() {
        return heapSize;
    }

    // 堆中是否存在某个key
    public boolean contains(T obj) {
        return indexMap.containsKey(obj);
    }

    public List<T> getAllElement() { // 获取所有元素
        List<T> ans = new ArrayList<>();
        for (T t : heap) {
            ans.add(t);
        }
        return ans;
    }

    // add
    public void push(T obj) {
        heap.add(obj);
        indexMap.put(obj, heapSize);
        heapInsert(heapSize++); // 下标为heapSize的地方为新元素
    }

    // pop:弹出第一个
    public T pop() {
        T ans = heap.get(0);
        swap(0, heapSize - 1);
        indexMap.remove(ans); // 反向索引表删除
        heap.remove(--heapSize); // 动态数组删除
        heapify(0);
        return ans;
    }

    // remove:C12_HeapEnhance删除任一一个对象
    public void remove(T obj) {
        T replace = heap.get(heapSize - 1);
        int index = indexMap.get(obj);//获取删除对象obj的位置
        indexMap.remove(obj); // 反向索引表要删除
        heap.remove(--heapSize);
        if (replace != obj) {
            heap.set(index, replace);
            indexMap.put(replace, index);
            relocation(replace);
        }
    }

    public T peek() {
        return heap.get(0);
    }

    public void relocation(T obj) {
        heapInsert(indexMap.get(obj));
        heapify(indexMap.get(obj));
    }


    // 一些工具类
    private void heapInsert(int index) { // 制定位置加入新值，向上比较；小根堆
        while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
            swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    private void heapify(int index) { // 制定位置加入新值，向下比较
        int left = 2 * index + 1;
        while (left < heapSize) {
            int exchage = (left + 1) < heapSize &&  comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? left+1 : left;
            exchage = comp.compare(heap.get(index), heap.get(exchage)) < 0 ? index : exchage;
            if (exchage == index) {
                break;
            }
            swap(index, exchage);
            index = exchage;
            left = 2 * exchage + 1;
        }
    }

    private void swap(int i, int j) {
        T ti = heap.get(i);
        T tj = heap.get(j);
        heap.set(i, tj);
        indexMap.put(tj, i);
        heap.set(j, ti);
        indexMap.put(ti, j);
    }

    @Override
    public String toString() {
        return "C12_HeapEnhance{" +
                "heap=" + heap +
                ", indexMap=" + indexMap +
                ", heapSize=" + heapSize +
                '}';
    }
}
